這章節會討論壓縮是怎麼一回事。

Prefix Code

基本上壓縮就是把原本比如8bit的字元，透過某種算法壓縮成小於8bit的字元，並套用到所有的字元，並且可以再透過某種算法還原成8bit字元，這樣就是壓縮與解壓了。不過在壓縮的時候，我們第一個遇到的問題就是，該如何用bit stream精準地表示壓縮後的各個字元呢？首先我們來用摩斯密碼表來看看：

會發現- - · - - · 可以有不同的翻譯，這樣就代表假設我們用摩斯密碼表來壓縮的話，就需要再想辦法做到prefix free的表示：

所以假若我們用以上這樣的樹狀結構，就可以做到prefix free了。

接著我們來看看不同的prefix code還有哪些可能：

或者

我們會發現，不同的字串假若用不同的prefix coding，會有不同的壓縮效率表現：

那該如何找到一個最讚最有效率的prefix code方法呢？以下會介紹兩種approach，其中一種是比較好的。

Shannon Fano Code

這種方法一開始我們先找出要壓縮內容中各個字元的出現次數：

然後次數比較多的擺在左側，用0代表；次數比較少的擺在右側，用1代表：

以此類推不斷演化這棵樹：

Huffman Coding

上面的方法看起來挺不錯的，但後來被Huffman Coding完全推翻了，證明出Huffman是全面性更好的方法：

從這個樹狀結構就可以發現，效率肯定是比Shannon Fano好的。

下面會分析使用Huffman Coding的話，每個字元平均會被幾個bit代表：

接著來討論實作面，在encoding的時候，適合用什麼資料結構呢：

以上提供了兩個可行的，其中可能array會是更簡潔的做法，但是核心概念上其實跟Map一樣，只是因為字元是可以一個蘿蔔一個坑的去對應到array的index。

接著來想想decoding會適合什麼資料結構呢：

答案是Tries，我們在decoding的時候可以很自然地透過Tries去找出bit stream中最後在Tries中會得到哪個字元。

而在實際上，我們會把分析內容後得出的Trie也放在decoding後的bit stream中，如下圖前面標示成紅字的bit stream：

Compression Theory

接著來討論一些關於壓縮議題更general的情況。

有沒有可能會有一個超屌的壓縮法，可以壓縮所有任何內容到50%？

第一個反對的論點是，假若是存在的，那所有的內容最後都可以壓縮到只剩一個bit，顯然不可能：

第二個反對論點，我們先假設說有2^1000個字元要壓縮，都是不同的字元哦，那使用最有效率的樹狀結構來存這個對應表，又要有50%的壓縮效率，代表只能有根 1 + 第一層 2 + 第二層 4 + …… + 2^500 = 2^501 - 1個壓縮後的表示，顯然不足！

代表會有將近一半的字元會沒辦法被這個樹狀結構encode：

接著討論如果我們想做一些特化的encoding方法，比如只用3個bit就代表了一整季的GameOfThrone：

解析出這個方法需要的bits：

那我們應該把我們要實作它的code也納進encoding後的結果中，這邊以java為例，所以我們的compression模型變成把java的code也放在壓縮內容中，並透過Interpreter，以java為例就是JVM，最後解壓出內容，這是實際上要做到特化的做法，其實需要考慮納進compression實作內容的大小，而不是可以好像很聰明的只剩下3個bits。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License